A quantizer is a device for converting numerical data into a finite number of possible outputs. That is, the input to a quantizer may be any value, but the output of a quantizer is limited to only certain values. The function of a quantizer is to determine which of its possible output values is closest to the input value and put out that value. For example, a flip-flop puts out either a voltage equal to the power supply voltage connected to the flip-flop (e.g., five volts or a logic one) or a voltage equal to the ground voltage connected to the flip-flop (e.g., zero volts or a logic zero). The input to a flip-flop may be any value between ground voltage and the power supply voltage. The flip-flop determines which of its two possible output values is closest to the input value and puts out that value. Typically, an input voltage greater than or equal to one-half of the power supply voltage will cause a flip-flop to put out the power supply voltage (i.e., a logic one) while an input voltage below one-half of the power supply voltage will cause a flip-flop to put out the ground voltage (i.e., a logic zero).
Quantizers are used in the design of signals for use over a noisy channel. Analog to Digital converters convert complex analog signals (e.g., 0.654783 V) into simplistic digital signals (e.g., logic 1). This is a form of data compression. An area centered at one of the allowable outputs is called a Voronoi region. If the quantizer receives a point in this region, it converts it, if necessary, to the allowable point in the center of the region.
Quantizers come in two types, scalar quantizers and vector quantizers. A scalar quantizer quantizes data from a single source by rounding a real number to its nearest output value (e.g., a flip-flop). A vector quantizer quantizes data from multiple sources by choosing one point from a finite set of points in n-dimensional space that is closest to the point represented by the input vector. A point in n-dimensional space is simply a string of n real numbers. That is, x=(x.sub.1, x.sub.2, x.sub.3, . . . , x.sub.n). For example, a point in three dimensional space is a point represented by three coordinates, a point in four dimensional space is a point represented by four coordinates, and so on. The allowed output values of a vector quantizer are called centroids.
The present invention concerns a lattice quantizer. A lattice in n-dimensional space is defined as follows. Let (v.sub.1, v.sub.2, . . . , v.sub.n) be a set of n linearly independent vectors in n-dimensional space. The lattice generated by (v.sub.1, v.sub.2, . . . , v.sub.n) is the set (c.sub.1 v.sub.1 +c.sub.2 v.sub.2 + . . . +c.sub.n v.sub.n), where c.sub.1, . . . , c.sub.n are integers. The vectors v.sub.1, v.sub.2, . . . , v.sub.n form a basis for the lattice. If X=(x.sub.1, x.sub.2, . . . , x.sub.n) then the norm of x is equal to (x.sub.1.sup.2 +x.sub.2.sup.2 + . . . +x.sub.n.sup.2). A sphere in n-dimensional space with center u=(u.sub.1, u.sub.2, . . . , u.sub.n) and radius p consists of all the points x=(x.sub.1, x.sub.2, x.sub.3, . . . , x.sub.n) satisfying (x.sub.1 -u.sub.1).sup.2 +(x.sub.2 -u.sub.2).sup.2 + . . . +(x.sub.n -u.sub.n).sup.2 =p.sup.2. A sphere packing is described by specifying the centers u and the radius p. When the centers of a group of spheres form a lattice, the packing is referred to as a lattice packing. A lattice packing always has a center at a point designated as an origin with the remaining centers on concentric spheres around the origin. The shells are numbered according to their proximity to the center or origin point. That is, the shell closest to the origin point is shell 1, the shell second closest to the origin point is shell 2, and so on. If one lattice may be obtained from another by rotation, reflection, or change of scale then it is said that the lattices are equivalent or similar.
Mathematicians continue to look for dense packings of n-dimensional spheres because there are important practical applications of sphere packing to problems arising in digital communications. A finite subset of the points on the surface of a sphere is called a spherical code. Spherical codes may be constructed from sphere packings. The sphere packing density of a lattice is defined by the number of spheres that fit within a particular volume. The kissing number of a lattice is defined as the number of spheres that a sphere in the lattice touches. The 24-dimensional lattice called the Leech lattice has the highest sphere packing density and the highest possible kissing number in 24 dimensions.
In a lattice quantizer, the centroids are grid points in n-dimensional space. The advantage of using a lattice quantizer is that the centroids are already known and do not have to be calculated from the input data. The disadvantage of using a lattice quantizer is that there are an infinite number of centroids. Because of this, lattice quantizers are only appropriate for quantizing data that has a probability distribution that is heavily concentrated around a single point in n-dimensional space (e.g., the origin).
Quantizing introduces error. The magnitude of the error is the distance from the received point to the acceptable point. The acceptable points are chosen to minimize the error, or more precisely, to minimize the mean squared error. For various dimensions, the mean squared error has been determined. It may be shown that higher dimension quantizers have lower errors per symbol than do lower dimension quantizers. Higher dimension quantizers with their lower errors provide better quantization than do lower dimension quantizers.
The Leech lattice has been extensively studied by mathematicians due to its connections to the fields of coding theory, combinatorics, and the classification of finite simple groups. As a result, a number of fast algorithms for finding the closest lattice point have been developed. These algorithms fall into two categories: maximum likelihood decoding and bounded distance decoding. Bounded distance decoding will not work in quantizer applications, since it only works for a received point within a small distance of a lattice point. Maximum likelihood decoding works for any received point and is well suited for a quantizer. A very fast algorithm is the algorithm described by Alexander Vardy and Yair Be'ery in "Maximum Likelihood Decoding of the Leech Lattice," IEEE TRANSACTIONS ON INFORMATION THEORY, Vol. 39, No. 4, July 1993, pp. 1435-1444. It takes only 3595 real operations in the worst case and 2955 operations on the average.
There has been a reluctance to use the Leech lattice in applications because of the large number of lattice points involved. Let shell i be set of points with norm 2i. Then there are no points in shell 1, but 196,560 points in shell 2 and 16,773,120 points in shell 3, etc. The present invention can transmit any Leech lattice point while only storing eighty-nine 24-bit codewords of the extended Golay code. An explicit method is given for transmission of points in shells 2 and 3, which can easily be extended to higher shells. This algorithm can be applied to the output of the algorithm of Vardy and Be'ery or any other algorithm for finding the closest point of the Leech lattice.
There are a number of advantages to using the Leech lattice as a quantizer. First, a number of fast algorithms have already been developed for finding the closest lattice point. Also, the Leech lattice has a smaller quantizer error than any known lattice of equal or lower dimension. U.S. Pat. No. 5,150,209, listing Richard L. Baker, Jeffrey Bernstein, Bernd Girod, Xiancheng Yuan, and Edmund Thompson as inventors, entitled "HEIRARCHICAL ENTROPY CODED LATTICE THRESHOLD QUANTIZATION ENCODING METHOD AND APPARATUS FOR IMAGE AND VIDEO COMPRESSION" discloses an eight dimensional lattice quantizer based on the E8 lattice. Each lattice point in E8 is sent using 9 bits for shell 1 or 12 bits for shell 2 lattice points. The present invention sends Leech lattice points with a maximum of 21 bits for shell 2 and 31 bits for shell 3 lattice points. (There are no shell 1 Leech lattice points.) The present invention uses fewer than 3 times the number of bits used to send the E8 lattice points, but the Leech lattice points contain 3 times as much information as the E8 lattice points. Although a smaller region of space is covered, the points are scaled before being input to the E8 lattice, and a similar procedure can be carried out for the Leech lattice. Finally, the E8 quantizer in the '209 patent, referenced above, stores 920 eight-long vectors of real numbers to keep track of 2400 lattice points. The present invention stores 89 twenty-four bit codewords to send the nearly 17 million points of shells 2 and 3, and by extension, any Leech lattice point.